1. Field of the Invention
The present invention relates to a method and apparatus for bag-to-set, buffering remembered set.
Sun, Sun Microsystems, the Sun logo, Solaris and all Java-based trademarks and logos are trademarks or registered trademarks of Sun Microsystems, Inc. in the United States and other countries. All SPARC trademarks are used under license and are trademarks of SPARC International, Inc. in the United States and other countries. Products bearing SPARC trademarks are based upon an architecture developed by Sun Microsystems, Inc.
2. Background Art
A xe2x80x9cremembered setxe2x80x9d is a set of objects that are represented in computer software. Normally the objects in the remembered set are objects that have been updated during a given time interval. Write barriers often are used to determine which objects belong in the remembered set. Before further discussing write barriers and their application to remembered sets, an overview of objects and object oriented programming is helpful.
Object-Oriented Programming
Object-oriented programming is a method of creating computer programs by combining certain fundamental building blocks, and creating relationships among and between the building blocks. The building blocks in object-oriented programming systems are called xe2x80x9cobjects.xe2x80x9d An object is a programming unit that groups together a data structure (one or more instance variables) and the operations (methods) that can use or affect that data. Thus, an object consists of data and one or more operations or procedures that can be performed on that data. The joining of data and operations into a unitary building block is called xe2x80x9cencapsulation.xe2x80x9d
An object can be instructed to perform one of its methods when it receives a xe2x80x9cmessage.xe2x80x9d A message is a command or instruction sent to the object to execute a certain method. A message consists of a method selection (e.g., method name) and a plurality of arguments. A message tells the receiving object what operations to perform.
One advantage of object-oriented programming is the way in which methods are invoked. When a message is sent to an object, it is not necessary for the message to instruct the object how to perform a certain method. It is only necessary to request that the object execute the method. This greatly simplifies program development.
Object-oriented programming languages are predominantly based on a xe2x80x9cclassxe2x80x9d scheme. The class-based object-oriented programming scheme is generally described in Lieberman, xe2x80x9cUsing Prototypical Objects to Implement Shared Behavior in Object-Oriented Systems,xe2x80x9d OOPSLA 86 Proceedings, September 1986, pp. 214-223.
A class defines a type of object that typically includes both variables and methods for the class. An object class is used to create a particular instance of an object. An instance of an object class includes the variables and methods defined for the class. Multiple instances of the same class can be created from an object class. Each instance that is created from the object class is the to be of the same type or class.
To illustrate, an employee object class can include xe2x80x9cnamexe2x80x9d and xe2x80x9csalaryxe2x80x9d instance variables and a xe2x80x9cset.sub.-salaryxe2x80x9d method. Instances of the employee object class can be created, or instantiated for each employee in an organization. Each object instance is the to be of type xe2x80x9cemployee.xe2x80x9d Each employee object instance includes xe2x80x9cnamexe2x80x9d and xe2x80x9csalaryxe2x80x9d instance variables and the xe2x80x9cset.sub.-salaryxe2x80x9d method. The values associated with the xe2x80x9cnamexe2x80x9d and xe2x80x9csalaryxe2x80x9d variables in each employee object instance contain the name and salary of an employee in the organization. A message can be sent to an employee""s employee object instance to invoke the xe2x80x9cset.sub.-salaryxe2x80x9d method to modify the employee""s salary (i.e., the value associated with the xe2x80x9csalaryxe2x80x9d variable in the employee""s employee object).
A hierarchy of classes can be defined such that an object class definition has one or more subclasses. A subclass inherits its parent""s (and grandparent""s etc.) definition. The parent class is also referred to as a xe2x80x9csuperclass.xe2x80x9d Each subclass in the hierarchy may add to or modify the behavior specified by its parent class. Some object-oriented programming languages support multiple inheritance where a subclass may inherit a class definition from more than one parent class. Other programming languages, such as the Java programming language, support only single inheritance, where a subclass is limited to inheriting the class definition of only one parent class. The Java programming language also provides a mechanism known as an xe2x80x9cinterfacexe2x80x9d which comprises a set of constant and abstract method declarations. An object class can implement the abstract methods defined in an interface.
An object is a generic term that is used in the object-oriented programming environment to refer to a module that contains related code and variables. A software application can be written using an object-oriented programming language whereby the program""s functionality is implemented using objects. As previously discussed, the encapsulation provided by objects in an object-oriented programming environment may be extended to the notion of components under a component model definition.
Write Barriers
Write barriers are inserted into computer programs so that the program can keep track of and/or trigger reactions when data items of interest are modified. Pages, objects, records, arrays, fields, array elements, documents, and paragraphs provide a few examples of data items that may be of interest when implementing a write barrier.
One application of a write barrier is for the tracking of inter-generational pointers in a garbage collector. A pointer is a memory address that indicates where data can be found. Garbage collection is a part of a language""s runtime system, or an add-on library, perhaps assisted by the compiler, the hardware, the operating system, or any combination of the three, that automatically determines what memory a program is no longer using, and recycles it for other use.
Often it is advantageous in garbage collection to know which pointers point from one generation to another (i.e., inter-generational pointers), or which pointers point from one area of memory to another area of memory. To find such pointers, one current scheme determines which pointers are already inter-generational. Then, when an object is updated, the garbage collector will only look at the inter-generational pointers to determine if they have been changed rather than looking at every pointer.
Another use of a write barrier is in the tracking of cache-resident objects in persistent object caching. In general, caches are implemented under the assumption that it is very likely that some object or piece of data will be repeatedly accessed. Access delays are minimized by keeping popular data close to the entity which needs it. Persistent objects are forms of data that continue to exist, even after the process that created them has stopped executing. When an executing process is using a persistent object there is a benefit to caching such an object, namely, the object can be accessed in memory rather than on disk and a memory access is quicker than a disk access.
In a garbage collector or a persistent object cache, all updates are recorded in the remembered set. Remembered sets are typically implemented using either a xe2x80x9cstore bufferxe2x80x9d technique or a xe2x80x9ccard markingxe2x80x9d technique.
Store Buffers
A store buffer is a stack of pointers to one or more updated entities. A store buffer can be a xe2x80x9cbagxe2x80x9d or a xe2x80x9csetxe2x80x9d. Updated entities are added to a bag immediately and every time an object is updated. Hence, a store buffer in the form of a bag may contain a plurality of duplicate entries for the same object as it is updated over time.
To be more efficient, some current schemes represent the remembered set with no duplicate entries. Using this approach, the remembered set is a true set and not a bag. To implement a store buffer in the form of a true set, objects are given a xe2x80x9cdirty markxe2x80x9d when added to the set. Then, if the object is updated again in the future, if the object has a dirty mark, it is not added again to the store buffer. With a true set, the scanning of entries is significantly more efficient.
One disadvantage in using a store buffer is that they require many additional instructions to implement the marking strategy. These many additional instructions add to the code needed to execute the computer program and are sometimes termed as causing a xe2x80x9ccode bloatxe2x80x9d. Store buffers are frequently used as remembered sets in interpreters, but not in compilers.
Card Marking
Using a card marking approach, a range of memory is defined. Then, evenly spaced chunks of memory are allocated. The size of the chunk, for instance, can be 512 or 1024 bytes. The specific size of the chunk, however, can vary with different implementations. Then, each chunk in memory is identified with a bit. By modifying the bit, for instance by assigning the bit a non-zero value, it indicates that a specific range of memory has been updated.
Systems that compile to machine code often use card marking, because much fewer instructions than a store buffer are needed to identify whether a much larger range of memory addresses has been updated. Thus, card marking causes less code bloat then store buffers. Card marking, however, creates a bag because although it takes little code bloat to identify which ranges have been updated, the code must still scan through the entire memory range to identify with specificity which objects have been updated.
In many instances, having a bag creates an even larger cost then the cost associated with bloated code, particularly in programs where updates are occurring frequently to a small subset of the objects in memory. Also, a true scan of the entire remembered set is relatively rare. For instance, a garbage collection or checkpoint operation, which may scan the entire remembered set, only occur occasionally in the life cycle of an executing computer process. In these instances, continually scanning ranges of memory for the same objects over and over is extremely disadvantageous and wasteful of computer resources.
Costs Associated with Write Barriers
Several costs are associated with the insertion of write barriers into program code. First, inserted write barrier instructions increase execution time. Second, adding write barrier instructions increases the amount of code in the computer program (i.e., code bloat). Finally, the execution time needed to process the data accumulated by write barriers increases (i.e., the program must handle the additional data in the store buffer).
The performance of code caching, including virtual memory (paging), suffers when code becomes bloated. In dynamic compilation systems, (Java technology environments, for instance), the code cache overflows more often, and thus, more frequent recompilations become necessary when the code becomes bloated.
A store buffer is typically scanned by garbage collection or persistent checkpointing to process each entity in the remembered set. If a computer program is to be responsive to user interaction, there is a limit to how long a user-observable progress pause like a garbage collection or a persistent checkpoint is allowed to take. As programs grow larger and larger, processing of large runtime system data sets, such as scanning remembered sets accumulated by write barriers, can become prohibitively slow. Thus, minimizing the execution time needed to process the data accumulated by write barriers is crucial.
When there is a large cost associated with having bloated code and the execution time of handling data related to the write barrier increases, current schemes become disadvantageous. A store buffer scheme whose write barrier can be implemented with as few instructions as required by typical card marking barriers would be attractive to compilation systems.
The present invention provides a method and apparatus for a bag-to-set, buffering remembered set. Card marking provides the ability to implement a write barrier with very few instructions. A store buffer provides fast and easy access to the updated objects observing the write barrier. One or more embodiments of the present invention combine the advantages of card marking and a store buffer to implement write barriers.
In accordance with the present invention, a remembered set is initially maintained as a bag. Then, at evenly spaced intervals over the execution of the computer program (or at other intervals), the bag is transformed into a set. By transforming the bag to a set at various intervals in the program""s execution, the user observable pause associated with write barrier code becomes minimal or non-existent. In addition, when a process uses the remembered set, a garbage collector or persistent checkpoint, for instance, the remembered set can be scanned more efficiently.
In one embodiment, the addresses of all updated objects are pushed to a thread local store buffer, which can take the form of a stack data structure. When the thread local stack overflows, the local stack is flushed to a global store buffer, which can also be a stack. In one embodiment, memory protection mechanisms determine when the thread local stack has overflowed. In another embodiment, a user trap is utilized to handle the overflowing of the thread local stack.
The threads comprise concurrent paths of execution within a single computer program. Thus, a plurality of threads that make up a single executing process may have their local stacks flushed to the global store buffer in the manner described by the invention. When flushing the local store buffer to the global store buffer, one embodiment of the invention uses a duplicate prevention scheme.
In the duplicate prevention embodiment, the global store buffer may contain free space after the local store buffer is flushed. If this happens, a local store buffer shrinking scheme is employed by an embodiment of the invention. In this embodiment, the local store buffer is re-allocated an amount of space to match the global store buffer""s contiguous free space. This re-allocation continues until the local store buffer""s space allocation falls below a predetermined and variable minimum threshold. When the minimum threshold is reached the local store buffer""s allocation is reset to the original allocation size and write barriers continue to be observed.